272. Closest Binary Search Tree Value II
Hard

Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. You may return the answer in any order.

You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

 

Example 1:

Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]

Example 2:

Input: root = [1], target = 0.000000, k = 1
Output: [1]

 

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 104.
  • 0 <= Node.val <= 109
  • -109 <= target <= 109

 

Follow up: Assume that the BST is balanced. Could you solve it in less than O(n) runtime (where n = total nodes)?

Accepted
72.4K
Submissions
135.7K
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
Consider implement these two helper functions:
  1. getPredecessor(N), which returns the next smaller node to N.
  2. getSuccessor(N), which returns the next larger node to N.
Show Hint 2
Try to assume that each node has a parent pointer, it makes the problem much easier.
Show Hint 3
Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
Show Hint 4
You would need two stacks to track the path in finding predecessor and successor node separately.

Average Rating: 4.20 (25 votes)

Premium

Solution


Overview

The problem is a BST variation of the "kth-smallest" classical problem. It is popular both in Google and Facebook, but these two companies are waiting for you to show different approaches to this problem. We're proposing 3 solutions here, and it's more an overview.

Prerequisites

Because of that, you might want first to check out the list of prerequisites:

Google vs. Facebook

There are three ways to solve the problem:

  • Approach 1. Sort, O(NlogN)\mathcal{O}(N \log N) time. The idea is to convert BST into an array, sort it by the distance to the target, and return the k closest elements.

  • Approach 2. Facebook-friendly, heap, O(Nlogk)\mathcal{O}(N \log k) time. We could use the heap of capacity k, sorted by the distance to the target. It's not an optimal but very straightforward solution - traverse the tree, push the elements into the heap, and then return this heap. Facebook interviewer would insist on implementing this solution because the interviews are a bit shorter than Google ones, and it's important to get problem solved end-to-end.

  • Approach 3. Google-friendly, quickselect, O(N)\mathcal{O}(N) time. Here you could find a very detailed explanation of quickselect algorithm. In this article, we're going to provide a relatively brief implementation. Google guys usually prefer the best-time solutions, well-structured clean skeleton, even if you have no time to implement everything in time end-to-end.


Approach 1: Recursive Inorder + Sort, O(N log N) time

Intuition

img Figure 1. Sort.

The most straightforward approach is to build inorder traversal and then find the k closest elements using build-in sort.

Algorithm

  • Build an inorder traversal array.

  • Find the k closest to the target elements using build-in sort.

Implementation

Complexity Analysis

  • Time complexity: O(NlogN)\mathcal{O}(N \log N). O(N)\mathcal{O}(N) to build inorder traversal and then O(NlogN)\mathcal{O}(N \log N) to sort it.

  • Space complexity: O(N)\mathcal{O}(N) to store list nums of NN elements.


Approach 2: Recursive Inorder + Heap, O(N log k) time

img Figure 2. Heap.

Algorithm

  • Instantiate the heap with "less close element first" strategy so that the heap contains the elements that are closest to the target.

  • Use inorder traversal to traverse the tree following the direction Left -> Node -> Right.

    • Push all elements into heap during the traversal, keeping the heap size less than or equal to kk.
  • As a result, the heap contains kk elements that are closest to target. Convert it into a list and return.

Implementation

Optimisations

One could optimize the solution by adding the stop condition. Inorder traversal pops the elements in the sorted order. Hence once the distance of the current element to the target becomes greater than the distance of the first element in a heap, one could stop the computations. The overall worst-case time complexity would be still O(Nlogk)\mathcal{O}(N \log k), but the average time could be improved to O(Hlogk)\mathcal{O}(H \log k), where HH is a tree height.

Complexity Analysis

  • Time complexity: O(Nlogk)\mathcal{O}(N \log k) to push N elements into the heap of the size kk.

  • Space complexity: O(k+H)\mathcal{O}(k + H) to keep the heap of k elements and the recursion stack of the tree height.


Approach 3: QuickSelect, O(N) time.

Hoare's selection algorithm

Quickselect is a textbook algorithm typically used to solve the problems "find kth something": kth smallest, kth largest, etc. Like quicksort, quickselect was developed by Tony Hoare, and also known as Hoare's selection algorithm.

It has O(N)\mathcal{O}(N) average time complexity and widely used in practice. It is worth to note that its worst-case time complexity is O(N2)\mathcal{O}(N^2), although the probability of this worst-case is negligible.

The approach is the same as for quicksort.

One chooses a pivot and defines its position in a sorted array in a linear time using the so-called partition algorithm.

As an output, we have an array where the pivot is on its perfect position in the ascending sorted array, sorted by the frequency. All elements on the left of the pivot are more close to the target than the pivot, and all elements on the right are less close or on the same distance from the target.

The array is now split into two parts. If by chance, our pivot element took kth final position, then kk elements on the left are these kk closest elements we're looking for. If not, we can choose one more pivot and place it in its perfect position.

img Figure 3. Quickselect.

If that were a quicksort algorithm, one would have to process both parts of the array. That would result in O(NlogN)\mathcal{O}(N \log N) time complexity. In this case, there is no need to deal with both parts since one knows in which part to search for kth closest element, and that reduces the average time complexity to O(N)\mathcal{O}(N).

Algorithm

The algorithm is relatively straightforward:

  • Traverse the tree and convert it into array nums.

  • Implement the simple function to compute the distance to the target. Note that the distance is not unique. That means we need a partition algorithm that works fine with duplicates.

  • Work with nums array. Use a partition scheme (please check the next section) to place the pivot into its perfect position pivot_index in the sorted array, move more close elements to the left of the pivot, and less close or of the same distance - to the right.

  • Compare pivot_index and k.

    • If pivot_index == k, the pivot is the kth less close element, and all elements on the left are the kk closest elements to the target. Return these elements.

    • Otherwise, choose the side of the array to proceed recursively.

Hoare's Partition vs. Lomuto's Partition

There is a zoo of partition algorithms. The most simple one is Lomuto's Partition Scheme.

The drawback of Lomuto's partition is that it fails with duplicates.

Here we work with an array of unique elements, but they are compared by the distances to the target, which are not unique. That's why we choose Hoare's Partition here.

Hoare's partition is more efficient than Lomuto's partition because it does three times fewer swaps on average, and creates efficient partitions even when all values are equal.

Here is how it works:

  • Move pivot at the end of the array using swap.

  • Set the pointer at the beginning of the array store_index = left.

  • Iterate over the array and move all more close elements to the left swap(store_index, i). Move store_index one step to the right after each swap.

  • Move the pivot to its final place, and return this index.

Implementation

Complexity Analysis

  • Time complexity: O(N)\mathcal{O}(N), O(N2)\mathcal{O}(N^2) in the worst case. Please refer to this card for the good detailed explanation of Master Theorem. Master Theorem helps to get an average complexity by writing the algorithm cost as T(N)=aT(N/b)+f(N)T(N) = a T(N / b) + f(N). Here we have an example of Master Theorem case III: T(N)=T(N2)+NT(N) = T \left(\frac{N}{2}\right) + N, that results in O(N)\mathcal{O}(N) time complexity. That's the case of random pivots.

    In the worst-case of constantly bad chosen pivots, the problem is not divided by half at each step, it becomes just one element less, that leads to O(N2)\mathcal{O}(N^2) time complexity. It happens, for example, if at each step you choose the pivot not randomly, but take the rightmost element. For the random pivot choice, the probability of having such a worst-case is negligibly small.

  • Space complexity: O(N)\mathcal{O}(N) to store nums.


Report Article Issue

Comments: 17
Kobe242424's avatar
Read More

How about the following solution? It visits all the nodes at most twice.

  1. Store all values into an array. If you do an inorder traversal the values should be sorted.
  2. Iterate through this array and find the single closest value to the target.
  3. Now you can have two pointers that begin from that closest value and expands to the left and right.
  4. You determine which way you expand by simply comparing the values of the left and right pointer.
    • If the left value is closer to the target then expand the left pointer by 1 and otherwise expand the right pointer by 1
var closestKValues = function(root, target, k) {

    // Simple inorder traversal to gather nodes
    let inorder= [];
    inorderSearch(root,inorder);
    if(inorder.length == 0)
        return;
    
    // grab difference of first first/smallest value
    let currDifference = Math.abs(target-inorder[0])
    let result = [];
    
    // start at index 1
    for(let i = 1; i < inorder.length; i++) {
        
        let prevDifference = currDifference;
        currDifference = Math.abs(target-inorder[i]);
        
        // basically says if you notice that you've arrived at the closest value to the target
        if(currDifference > prevDifference || i == inorder.length-1) {
            let left = null, right = null;
            
            if(Math.abs(inorder[i-1]-target) < Math.abs(inorder[i]-target)  ) {
                left = i-1, right = i-1;
            } else {
                left = i, right = i;
            }
            
            // push the one single value that's closest to the target
            result.push(inorder[right]);
            
            // start expanding left and right until the total is k
            while(right-left+1 < k && (right < inorder.length-1 || left > 0) ) {
                let rv = inorder[right+1];
                let lv = inorder[left-1];
                
                if(right < inorder.length-1 && left > 0) {
                    let ld = Math.abs(target-lv), rd = Math.abs(target-rv);
                    if(ld < rd) {
                        result.push(lv);
                        left--;
                    } else {
                        result.push(rv);
                        right++;
                    }
                } else if(right < inorder.length-1) {
                    result.push(rv);
                    right++;
                } else {
                    result.push(lv);
                    left--;
                }
                
            }
            
            // you only need to run this while loop once so break once you're done
            break;
        }
        
    }
    
    return result.length == 0  ? inorder : result;
};

function inorderSearch(root, inorder) {
    if(root == null)
        return;
    
    inorderSearch(root.left, inorder);
    inorder.push(root.val);
    inorderSearch(root.right, inorder);
}

13
Show 6 replies
Reply
Share
Report
Ashna's avatar
Read More

It could be done in O(N) Time and O(K) Space with inorder and using a deque.
It's just like a sliding window.

class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {          
        Deque<Integer> deque = new LinkedList<>();
        inorder(deque, root, target, k);
        return new ArrayList(deque);
    }
    
    private void inorder(Deque<Integer> deque, TreeNode node, double target, int k) {
        if (node == null)
            return;
        inorder(deque, node.left, target, k);
        double val = Double.valueOf(node.val);
        if (deque.size() == k) {
            if (Math.abs(Double.valueOf(deque.peekFirst())-target) > Math.abs(val - target)) {
                deque.pollFirst();
                deque.addLast(node.val);
            } else return;
        } else {
            deque.addLast(node.val);
        }
        inorder(deque, node.right, target, k);
    }
}

3
Show 1 reply
Reply
Share
Report
__thalaiva__'s avatar
Read More

@andvary Great solution and analysis. I assume Facebook looks for most optimized solution as well. Would it help to implement Quick select for facebook interview?

2
Show 6 replies
Reply
Share
Report
zhusiwei93's avatar
Read More

why inorder traversal takes O(nlogn)? Isn't it just O(n)?

2
Show 8 replies
Reply
Share
Report
Joe_Smith's avatar
Read More

I'll never understand some of these difficulty level settings. This is basically a traversal with a max heap added in, not really a "hard". In other places, they have some DPs as "easy" which seems crazy.

2
Show 1 reply
Reply
Share
Report
guoyang328's avatar
Read More

If I'm not mistaken, the QuickSelect solution uses Lomuto partition rather than Hoare's, whereas it claims to use the latter.

1
Show 1 reply
Reply
Share
Report
rahulkun's avatar
Read More

I think first two approaches are sub-optimal sorting already sorted data set.

1
Reply
Share
Report
neham's avatar
Robert-Lu's avatar
Read More

I think there is a very simple O(N) solution. No any extra advanced data structure. Just two pointers.

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        L = []
        def inorder(n):
            if n:
                inorder(n.left)
                L.append(n.val)
                inorder(n.right)
        inorder(root)
        
        D, p = [], None
        for i, n in enumerate(L):
            D.append(abs(n - target))
            if p is None or D[p] > D[-1]:
                p = i
                
        l, r = p, p
        while r - l + 1 < k:
            if l == 0:
                r += 1
            elif r == len(D) - 1:
                l -= 1
            elif D[r+1] > D[l-1]:
                l -= 1
            else:
                r += 1
        
        return L[l:r+1]

0
Reply
Share
Report
Goldspear's avatar
Read More

The article is well-written for the listed solutions, but misleading for not covering other more optimal options.

Given it's about finding a target in BST, binary search is the most obvious route and guarantees the performance. The only tricky part is to expand from the closest node to the closest K nodes, which has some trade-offs to consider :

  1. Speed over space: in order to quickly expand from closest 1 to K, using an aux array is the way to go Time O(N), Space O(N); this approach is fairly straightforward to implement.
  2. Space over speed: binary search to find the closest node, and use the predecessor and successor pattern to expand to the next nodes (using a parent pointer, both could be done in O(logN) on average). Time O(KlogN), Space O(1), since only a few pointers are needed besides the result. Note this is still a lot better than O(NlogK) of the Inorder + Heap approach, but a bit lengthy to implement.

Imo the above layer qualifies this problem as a "hard", and just because test cases all passed with all sub-optimal solutions doesn't change the difficulty level of the problem itself.

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium